package l.l.w.CodingInterviews;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created by llw on 2018/4/9/0009.
 */
public class 数据流中的中位数 {
    int count = 1;
    PriorityQueue<Integer> minDump = new PriorityQueue<Integer>(new Comparator<Integer>(){
        public int compare(Integer o1, Integer o2){
            return o1 - o2;
        }
    });
    PriorityQueue<Integer> maxDump = new PriorityQueue<Integer>(new Comparator<Integer>(){
        public int compare(Integer o1, Integer o2){
            return o2 - o1;
        }
    });
    public void Insert(Integer num) {
        if((count & 1) == 1){    //奇数的时候
            minDump.offer(num);
            maxDump.offer(minDump.poll());
            count++;
        }else{                 //偶数的时候
            maxDump.offer(num);
            minDump.offer(maxDump.poll());
            count++;
        }
    }

    public Double GetMedian() {
        if((count & 1) == 0){    //奇数.因为count++了，所以颠倒了
            return maxDump.peek() + 0.0;
        }else{
            return (minDump.peek() + maxDump.peek()) / 2.0;
        }
    }

    public static void main(String[] args) {
        int[] nums = {5,2,3,4,1,6,7,0,8};
        数据流中的中位数 obj = new 数据流中的中位数();
        for(int i = 0; i < nums.length; ++i){
            obj.Insert(nums[i]);
            System.out.println(obj.GetMedian());
        }
    }
}
